#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;

int t, k, n;
string s;
map<char, int> mp;
int solve() {
    int x = 0, y = 0;
    for (char i = 'a'; i <= 'z'; i++) {
        if (mp[i]) {
            x += mp[i]/2;
            y += mp[i] % 2;
        }
    }

    int flag = 0;
    ll res = x/k*2ll;
    while(false) {

    }
    if (x%k * 2ll  >= k-y) flag = 1;
    return res+flag;
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin >> t;
    while (t--) {
        cin >> n >> k >> s;
        mp.clear();

        for (auto ch : s) {
            mp[ch]++;
        }
        cout << solve() << endl;
    }
    return 0;
}